/// @tags:
#include <cctype>
#include <cmath>
#include <cstdio>
#include <tr1/unordered_map>

namespace BlueQuantum {

typedef long long ll;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

int n, T, p;
std::tr1::unordered_map<int, int> map;

inline ll qpow(ll base, int exp) {
  ll res = 1;
  while (exp) {
    if (exp & 1) res = res * base % p;
    base = base * base % p;
    exp >>= 1;
  }
  return res;
}

int exGCD(int a, int b, int &x, int &y) {
  if (!b) return x = 1, y = 0, a;
  int gcd = exGCD(b, a % b, y, x);
  y -= a / b * x;
  return gcd;
}

/// @brief a^n = b (mod p)
int BSGS(int a, int b) {
  map.clear();
  if (b == 1) return 0;
  if (a % p == 0) return b ? -2 : 1;
  int m = ceil(sqrt(p));
  for (int j = 0, mul = b; j < m; ++j, mul = 1ll * mul * a % p) map[mul] = j;
  std::tr1::unordered_map<int, int>::iterator iter;
  for (int j = 1, mul = qpow(a, m), k = mul; j <= m; ++j, mul = 1ll * mul * k % p) {
    if ((iter = map.find(mul)) != map.end()) return j * m - iter->second;
  }
  return -2;
}

inline int main() {
  read(T);
  for (int a, b, x, t; T; --T) {
    read(p), read(a), read(b), read(x), read(t);
    if (x == t) puts("1");
    else if (a == 0) {
      printf("%d\n", x == t ? 1 : (b == t ? 2 : -1));
    } else if (a == 1) {
      int _x, _y, d = t - x < 0 ? t - x + p : t - x;
      int gcd = exGCD(b, p, _x, _y);
      if (d % gcd) puts("-1");
      else {
        _x = 1ll * _x * d / gcd % p;
        _x = ((_x + 1) % p + p) % p;
        printf("%d\n", _x ? _x : p);
      }
    } else {
      int a1 = (1 - a + p) % p;
      printf("%d\n", BSGS(a, ((1ll * a1 * t % p - b + p) % p) *
                                 qpow((1ll * a1 * x % p - b + p) % p, p - 2) % p) +
                         1);
    }
  }
  return 0;
}

}  // namespace BlueQuantum

signed main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P3306 [SDOI2013] 随机数生成器.in", "r", stdin);
  freopen("P3306 [SDOI2013] 随机数生成器.out", "w", stdout);
#endif
#endif

  return BlueQuantum::main();
}